Math 512: Finite Model Theory Games

February 27, 1997

We work in a finite relational language.

For m ≤ ω a game G_{m}(A, B) played by two players, duplicator and spoiler, consists of m turns. On move k, Spoiler chooses an element from A or B (denoted by a_{k} or b_{k} respectively). Duplicator then chooses an element from the other structure (denoted by b_{n} or a_{n} respectively). Duplicator wins if the sequences ⟨a_{i} : i < m⟩ and ⟨b_{i} : i < m⟩ are partially isomorphic.

0.1 Definition. 1. A ≃_{m} B if duplicator has a winning strategy for the family of games: G_{m}(A, B).

2. A ≡_{m} B if A and B satisfy the same formulas of quantifer rank m.

3. A ≃ =_{n} B is defined by induction:

(a) A ≃ =_{0} B iff A ≡_{0} B.

(b) A ≃ =_{n+1} B iff

i. For every a ∈ A there is b ∈ B such that (A, a) ≃ =_{n} (B, b) and

ii. For every b ∈ B there is a ∈ A such that (A, a) ≃ =_{n} (B, b).

Remark: A ≃_{0} B iff A ≡_{0} B. This holds just if the quanifier free diagrams of the the constants are the same.

0.2 Lemma. For all n < ω, A ≃_{n} B iff A ≃ =_{n} B.

Proof. Induct on n; 0 is clear. Moreover, A ≃ =_{n} B implies A ≃_{n} B is clear. So suppose duplicator has a winning strategy in G_{n+1}(A, B). Fix a_{0} arbitrary in A. If duplicator chooses b_{0} by his winning strategy then duplicator has a winning strategy in G_{n}((A, a_{0}), (B, b_{0})) and we finish by induction.

0.3 Definition. The rank-m type of a k-tuple \overline{a} ∈ A,

tp_{A}^{m}(\overline{a}) = \{ϕ(\overline{x}) : A ⊧ ϕ(\overline{a}) & qd(ϕ) ≤ m\}.

Note that for a finite relational language and m < ω, the existential quantification of this type is a sentence ϕ_{m} with quantifier rank m + 1;

0.4 Theorem. For all A, B in all finite relational langauages and m < ω, the following are equivalent:

1. A ≡_{m} B.

2. A ≃ =_{n} B.

3. A ≃_{m} B.

4. A and B realize the same rank-(m − 1)-types of singletons.

Proof. We have already noticed the equivalence of 2 and 3. Moreover, we have seen m = 0 in 0.1. Assume the equivalence at n; we prove n + 1. First, we show 1 implies 4. So A ≡_{n+1} B. We must show A and B realize the same rank-n types of singletons. For arbitrary a ∈ A, we must find b ∈ B such that tp_{A}^{n}(a) = tp_{B}^{n}(b). Note that the sentence ϕ_{n} determining tp_{A}^{n}(a) has quantifier rank n + 1. So it is satisfied by B and we can find a realization in B. Reversing the roles of A and B, we see B realizes exactly the rank-n types of singletons realized in A.

Now we show 4 implies 2. Suppose A and B realize the same rank-n types of singletons; we want A ≃ =_{n} B. Pick an arbitrary a ∈ A. Choose b ∈ B with tp_{A}^{n}(a) = tp_{B}^{n}(b). So, (A, a) ≡_{n} (B, b). By induction, (A, a) ≃ =_{n} (B, b), as required. The other direction is symmetric.

Finally, we show 2 implies 1. Assume A ≃ =_{n+1} B. Every formula of quantifier rank n+1 is a Boolean combination of formulas of the form: (∃x)ψ(x), where ψ has quantifier rank at most n. So it suffices to show that for each formula σ of that form.

A ⊧ σ iff B ⊧ σ.

Fix such a σ and suppose witnessed by a in A. Since, A ≃ =_{n+1} B. we can choose b ∈ B with (A, a) ≃ =_{n} (B, b). By induction, (A, a) ≡_{n} (B, b), so B ⊧ σ. The argument is symmetric for the case B ⊧ σ.

This formalization of the argument was based largely on notes by Chris Laskowski.